package com.formula.datastructure.exercise.graph.undirect.mst;

import com.formula.datastructure.exercise.graph.undirect.*;

// 最小生成树只有无向图
public class Prim {
    private static int INF = 99999;

    public ListEdge[] getMST(ListGraph graph) {
        int N = graph.vertexSize();
        ListEdge[] treeEdges = new ListEdge[N - 1];
        ListVertex[] addedVers = new ListVertex[N];
        addedVers[0] = graph.vertexList[0];
        /**
         * 一共有3层
         * 1层for就是需要找N-1次
         * 2层for就是对已经加入的顶点所有边遍历
         * 3层, 对于邻接表, 用while找出这个点的最短边
         */
        for (int i = 0; i < N - 1; i++) {

            int min = INF;
            int from = 0;
            int to = 0;
            for (int j = 0; j < N; j++) {
                /**
                 * 找出这样的边：
                 * 1. 可以加入新的节点当中
                 * 2. 最短的边
                 */
                if (addedVers[j] != null) {
                    ListEdge tempEdge = addedVers[j].firstEdge;
                    while (tempEdge != null) {
                        if (addedVers[tempEdge.toIdx] == null && tempEdge.weight < min) {
                            min = tempEdge.weight;
                            treeEdges[i] = tempEdge;
                            from = j;
                            to = tempEdge.toIdx;
                        }
                        // 这个千万不要写到if语句里面了
                        tempEdge = tempEdge.nextEdge;
                    }
                }
            }
            addedVers[to] = graph.vertexList[to];
            System.out.println("From: " + addedVers[from].data + ", To :" + addedVers[to].data + ", weight : " + treeEdges[i].weight);
        }
        return treeEdges;
    }

    /**
     * 邻接矩阵才是正解, 因为可以很方便的实现
     * 时间复杂度O(n^2)
     *
     * @param graph
     */
    public void getMST(MatrixGraph graph) {
        int N = graph.vertex.length;
        int[] shortest = new int[N];
        int[] visited = new int[N];

        visited[0] = 1;

        for (int i = 0; i < N; i++) {
            shortest[i] = graph.edges[0][i];
        }


        /**
         * 记忆方法:
         * 一个for里面两个for
         * 都有visited
         * 第一次找出点
         * 第二次更新边
         */
        for (int i = 0; i < N - 1; i++) {
            int min = INF;
            int nextVer = 0;
            for (int j = 0; j < N; j++) {
                if (visited[j] == 0 && min > shortest[i]) {
                    min = shortest[i];
                    nextVer = j;
                }
            }

            visited[nextVer] = 1;

            for (int j = 0; j < N; j++) {
                if (visited[j] == 0 && graph.edges[nextVer][j] < shortest[j]) {
                    shortest[j] = graph.edges[nextVer][j];
                }
            }
        }

    }

    /**
     * 用传统的办法来做
     * @param graph
     */
    public void getMST2(MatrixGraph graph) {

    }

    public static void main(String[] args) {
        testListGraph();
    }

    public static void testListGraph() {
        ListGraph graph = new ListGraph();
        ListVertex A = new ListVertex("A");
        ListVertex B = new ListVertex("B");
        ListVertex C = new ListVertex("C");
        ListVertex D = new ListVertex("D");
        ListVertex E = new ListVertex("E");
        ListVertex F = new ListVertex("F");

        ListEdge edge1 = new ListEdge(1, 5);
        ListEdge edge2 = new ListEdge(3, 9);
        A.addEdge(edge1);
        A.addEdge(edge2);

        ListEdge edge3 = new ListEdge(2, 2);
        ListEdge edge4 = new ListEdge(3, 10);
        B.addEdge(edge3);
        B.addEdge(edge4);

        ListEdge edge5 = new ListEdge(4, 8);
        ListEdge edge6 = new ListEdge(5, 7);
        C.addEdge(edge5);
        C.addEdge(edge6);

        ListEdge edge7 = new ListEdge(4, 4);
        D.addEdge(edge7);


        ListEdge edge8 = new ListEdge(5, 7);
        E.addEdge(edge8);

        ListEdge edge9 = new ListEdge(1, 6);
        F.addEdge(edge9);

        graph.insertVex(A);
        graph.insertVex(B);
        graph.insertVex(C);
        graph.insertVex(D);
        graph.insertVex(E);
        graph.insertVex(F);

        Prim prim = new Prim();
        prim.getMST(graph);
    }
}
